package com.yao.code;

import com.yao.tool.TreeNode;

/**
 * @author yaoquanwei
 * @date 2021/8/26 21:32
 */
public class Code210826 {
    /**
     * 剑指offer 64.求1+2+。。。n
     * 不准使用乘除法，for、while、if、else、switch、case等关键字及条件判断语句
     *
     * @param n
     * @return
     */
    public int sumNums(int n) {
        return (int) (Math.pow(n, 2) + n) >> 1;
    }

    /**
     * 剑指offer 68.二叉搜索树的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val > q.val) {
            TreeNode tem = p;
            p = q;
            q = tem;
        }
        if (root.val > q.val) {
            return lowestCommonAncestor1(root.left, p, q);
        } else if (root.val < p.val) {
            return lowestCommonAncestor1(root.right, p, q);
        }
        return root;
    }

    /**
     * 剑指offer 68.二叉树的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
    }
}
